心之所向便是光

Leetcode 114.二叉树展开为链表

  • 2021-06-25
  • 作者 Ender
  • 3.24K 字
  • 次阅读

题目描述：

给你二叉树的根结点 root ，请你将它展开为一个单链表。

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

示例 1：

1
2
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [0]
输出：[0]

提示：

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

链接：

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

题目分析

1.前序遍历

  如果先不考虑进阶的要求，我们可以直接按照先序遍历的顺序遍历一次二叉树，将其所有结点逐一添加到数组中，然后再逐一进行连接。（如果采用迭代的方法遍历二叉树则还可以边遍历边连接）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    void preorder(vector<TreeNode*>& list, TreeNode* root){
        if(!root) return;
        list.push_back(root);
        preorder(list, root->left);
        preorder(list, root->right);
    }
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> list;
        preorder(list, root);
        TreeNode *pre = root;
        for(int i = 1; i < list.size(); i++){
            pre->left = nullptr;
            pre->right = list[i];
            pre = pre->right;
        }
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们遍历一次二叉树，重新连接了一次二叉树。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们需要一个大小为 $n$ 的数组存放二叉树结点。

2.寻找前驱结点

  进阶的要求如何达到呢？我们如果能够直接在原树进行连接，则不需要额外空间。最终的树是按照前序遍历的顺序逐一连接到右子树中的，而前序遍历的顺序是 [根结点 左子树 右子树]。如果当前结点左子树为空，则与最终结果一样，无需进行操作。如果当前结点左子树不为空，则当前结点右子树应该是在左子树访问完毕后才进行访问，这个时候，右子树的前驱结点应该就是左子树的最右叶子。我们寻找到这个前驱结点，并将当前结点的右子树作为前驱结点的右子树连接，同时将当前结点的左子树变为右子树。如此处理所有的结点。
  如下面例子（第一棵树）所示，1 有左子树，我们找到左子树的最右叶子 4，并将 1 的右子树 [5, 6] 连接到 4 之后，如第二棵树所示。然后再将左子树根结点 2 变为 1 的右子树，如第三棵树所示。这个时候就处理好了 1 这个结点，接下来以同样的流程处理 2 这个结点。如第四第五颗树所示。

1
2
3
4
5
6
7
8
9
10
11
    1                 1             1                  1              1
   / \               /               \                  \              \
  2   5             2                 2                  2              2
 / \   \           / \               / \                /                \
3   4   6         3   4             3   4              3                  3
                       \                 \              \                  \               
                        5                 5              4                  4
                         \                 \              \                  \
                          6                 6              5                  5
                                                            \                  \
                                                             6                  6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *now = root;
        while(now != nullptr){
            if(now->left != nullptr){
                TreeNode *pre = now->left;
                while(pre->right != nullptr){
                    pre = pre->right;
                }
                pre->right = now->right;
                now->right = now->left;
                now->left = nullptr;
            }
            now = now->right;
        }
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们对于每个结点都需要访问一次进行处理，而寻找前驱结点的过程中每个结点至多被访问一次。
  空间复杂度：$O(1)$。这个算法为原地算法，我们只需要常数的空间存放若干变量。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-26